数组、Map、Set、List集合差别及联系详解 |
您所在的位置：网站首页 › list set和map区别 › 数组、Map、Set、List集合差别及联系详解 |
数组、Map、Set、List集合差别及联系详解
|
Array（数组）和集合的区别：
(1)数组是大小固定的，并且同一个数组只能存放类型一样的数据（基本类型/引用类型）
(2)JAVA集合可以存储和操作数目不固定的一组数据。
(3)若编程时不知道究竟需要多少对象，需要在空间不足时自动扩增容量，则需要使用容器类库，array不适用。
FYI：使用相应的toArray()和Arrays.asList()方法可以相互转换。
java容器类类库（Collection和Map） Java容器类类库的作用是保存对象，并将其划分为两个不同的概念： 1）Collection（接口） 一个独立元素的序列，这些元素都服从一条或多条规则。 List必须按照插入的顺序保存元素，而Set不能有重复的元素，Queue按照排队规则来确定对象产生的顺序（通常与它们被插入的顺序相同） 主要方法：add,equals,hashCode,remove,clear ,size，iterator等 2）Map（接口） 又称为关联数组，是一组成对的“键值对”对象，使用键对象来查找值对象。 主要方法：get,equals,clear,hashCode,put,remove,size等 四种容器：List，Set，Map，Queue，均为接口，除Map外，都继承了Collection接口，所以都拥有Collection中的方法 一、List 1、List的实现：ArrayList，LinkedList ArrayList：主要用于随机访问大量元素，但是在List的中间插入和移除元素时较慢，按照插入的顺序保存元素，其底层实现是数组 LinkedList：可以以较低的代价在List中间进行插入和删除操作，按照插入的顺序保存元素，其底层实现是链表 List的主要方法：除继承了Colloction内的方法还扩展了get,set等方法。 2、List的选择 在LinkedList的插入和移除代价相当低廉，并且不随列表尺寸发生变化，这是因为在LinkedList中插入元素时只需链接新的元素，而不必修改链表中剩余的元素， 但在ArrayList中插入元素时代价特别高，并且其代价随链表尺寸的增加而增加，这是因为在ArrayList插入元素时，必须创建空间并将它的所有引用向前移动。 二、Set 1、Set的实现：HashSet, TreeSet, LinkedHashSet HashSet:为快速查找而定义的Set，存入Hash Set的元素必须定义hashCode(),即散列函数。 TreeSet：保持次序的Set，底层为红-黑数结构，使用它可以从Set中提取有序的序列，元素必须实现Comparable接口。 LinkedHashSet：拥有HashSet的查询速度，所以也使用了散列函数，内部使用了链表来维护元素的插入顺序，所以在使用迭代器遍历Set时，结果会按元素的插入的次序显 示。元素也必须定义hashCode（）方法。 Set的主要方法：除了继承了Collection内的方法，没有额外功能。 2、Set的选择 HashSet的性能基本上总是比TreeSet好，特别是在添加和查询元素时。TreeSet存在的唯一原因是它可以维持元素的排序状态，所以只有当需要一个排好序的Set时，才应该 使用TreeSet.因为TreeSet内部结构支持排序，并且因为迭代是我们更有可能执行的操作，所以用TreeSet迭代通常比HashSet要快。对于插入操作，LinkedHashSet比 HashSet的代价更高，这是由维护链表所带来的额外开销造成的。 3、SortedSet：其中的元素可以保证处于排序状态，按对象的比较函数对元素进行排序而不是插入顺序，TreeSet是其实现。 三、Map 1、Map的实现：HashMap , TreeMap, LinkedHashMap, WeakHashMap，ConcurrentHashMap，IdentityHashMap HashMap：提供了最快的查找技术，基于散列表的实现，取代了HashTable，插入和查询“键值对”的开销是固定的。可以通过构造器设置容量和负载因子，以调整容 器的性能。必须有hashCode（）和equals（）方法。 TreeMap：基于红-黑树的实现，查看“键”或“键值对”时，它们会被排序(次序由Comparable或Comparator决定)。按照比较结果的升序保存键，所得到的结果是 经过排序的。TreeMap是唯一的带有subMap（）方法的Map，它可以返回一个子树。必须实现Comparable接口。 LinkedHashMap：类似于HashMap，但是迭代遍历是时取得“键值对”的顺序是其插入次序，或者是最近最少使用（LRU）的次序，只比HashMap慢一点，而在 而在迭代访问时反而更快，因为它使用链表维护内部次序。必须实现hashCode（）和equals（）。 WeakHashMap：弱键映射，允许释放映射所指向的对象，这是为解决某类特殊问题而设计的。如果映射之外没有引用指向某个“键”，则此键可以被垃圾收集器回收 ConcurrentHashMap：一种线程安全的Map，它不涉及同步加锁。 IdentityHashMap：使用==代替equals（）对“键”进行比较的散列映射。专为解决特殊问题而设计的。 2、Map的选择 使用Map时，第一选择应该是HashMap，只有在要求Map始终保持有序时，才需要使用TreeMap。 LinkedHashMap在插入时比HashMap慢一点，因为它维护散列数据结构的同时还要维护链表（以保持插入顺序），正是由于这个链表，使其迭代速度更快。 3、SortedMap：TreeMap是其唯一实现，可以确保键处于排序状态。 四、Queue： 1、队列是先进先出（FIFO）的容器，只能从一端放入，从另一端取出。由于LinkedList添加了可以使其用作栈、队列或双端队列的方法，所以可以用LinkedList实现Queue 接口， Queue接口中的方法：offer（），peek（）和element（）在不移除的情况下返回队头，poll（）和remove（）将移除并返回队头。 2、PriorityQueue：优先级队列声明下一个弹出元素是最需要的元素（具有最高的优先级）。 3、双向队列：可以在任何一端添加或移除。 五、Java 1.0/1.1的容器（尽量避免使用以下容器） 1、Vector：唯一可以自我扩展的序列，但缺点过多 2、Enumeration：迭代器的新名字–枚举，它比Iterator接口小。 3、HashTable：用HashMap代替。 4、Stack：继承了Vector。 六、散列和散列码 散列的价值在于速度，散列使得查询得以快速进行。存储一组元素最快的数据结构是数组，所以使用数组来存储键的信息。数组并不保存键本身，而是通过键对象生成一个数字， 将其作为数组的下标，这个数字就是散列码，由定义在Object中的、且可能由你的类覆盖的hashCode（）方法生成。不同的键可以产生相同的下标，所以解决了数组容量被固定 的问题，但同时可能会由冲突。通常，冲突由外部链接处理：数组并不直接保存值，而是保存值的list，然后队list中的值使用equals（）方法进行线性查询。默认的hashCode 产生的散列码是对象的地址，而在实际程序中不一定是将地址作为散列码，所以需要覆盖hashCode（）方法，同时需要覆盖equals（）方法来比较当前的键与表中的键是否相 同，因为equals（）默认比较的是对象的地址，而键不一定总是由地址构成。**一、集合 集合类存放于java.util包中。 集合类存放的都是对象的引用，而非对象本身，出于表达上的便利，我们称集合中的对象就是指集合中对象的引用（reference)。 集合类型主要有3种：set(集）、list(列表）和map(映射)。 一、这三者什么关系呢 Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map ├Hashtable ├HashMap └WeakHashMap
iterator接口: Set接口同样是Collection接口的一个子接口，它表示数学意义上的集合概念。Set中不包含重复的元素，即Set中不存两个这样的元素e1和e2，使得e1.equals(e2)为true。由于Set接口提供的数据结构是数学意义上集合概念的抽象，因此它需要支持对象的添加、删除，而不需提供随机访问。故Set接口与Collection的接口相同。 Set接口继承Collection接口，而且它不允许集合中存在重复项。所有原始方法都是现成的，没有引入新方法。具体的Set实现类依赖添加的对象的equals()方法来检查等同性。 HashSet： 使用HashMap的一个集的实现。虽然集定义成无序，但必须存在某种方法能相当高效地找到一个对象。使用一个HashMap对象实现集的存储和检索操作是在固定时间内实现的. TreeSet： 在集中以升序对对象排序的集的实现。这意味着从一个TreeSet对象获得第一个迭代器将按升序提供对象。TreeSet类使用了一个TreeMap. 为优化 HashSet 空间的使用，您可以调优初始容量和负载因子。TreeSet 不包含调优选项，因为树总是平衡的，保证了插入、删除、查询的性能为log(n)。 HashSet 和 TreeSet 都实现 Cloneable 接口。 当您要从集合中以有序的方式抽取元素时，TreeSet实现会有用处。为了能顺利进行，添加到TreeSet的元素必须是可排序的。 Set的演示： import java.util.*; public class SetExample { public static void main(String args[]) { Set set = new HashSet(); set.add("Bernadine"); set.add("Elizabeth"); set.add("Gene"); set.add("Elizabeth"); set.add("Clara"); System.out.println(set); Set sortedSet = new TreeSet(set); System.out.println(sortedSet); } }运行程序产生了以下输出。请注意重复的条目只出现了一次，列表的第二次输出已按字母顺序排序。 [Gene, Clara, Bernadine, Elizabeth] [Bernadine, Clara, Elizabeth, Gene]3.List List接口继承了Collection 接口以定义一个允许重复项的有序集合。该接口不但能够对列表的一部分进行处理，还添加了面向位置的操作。 实际上有两种List: 一种是基本的ArrayList,其优点在于随机访问元素，另一种是更强大的LinkedList,它并不是为快速随机访问设计的，而是具有一套更通用的方法。 List : 次序是List最重要的特点：它保证维护元素特定的顺序。List为Collection添加了许多方法，使得能够向List中间插入与移除元素(这只推荐LinkedList使用。)一个List可以生成ListIterator,使用它可以从两个方向遍历List,也可以从List中间插入和移除元素。 ArrayList : 由数组实现的List。允许对元素进行快速随机访问，但是向List中间插入与移除元素的速度很慢。ListIterator只应该用来由后向前遍历ArrayList,而不是用来插入和移除元素。因为那比LinkedList开销要大很多。 LinkedList : 对顺序访问进行了优化，向List中间插入与删除的开销并不大，随机访问则相对较慢。(使用ArrayList代替。)还具有下列方法：addFirst(), addLast(), getFirst(), getLast(), removeFirst() 和 removeLast(), 这些方法 (没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈、队列和双向队列使用。 Vector：实现一个类似数组一样的表，自动增加容量来容纳你所需的元素。使用下标存储和检索对象就象在一个标准的数组中一样。你也可以用一个迭代器从一个Vector中检索对象。Vector是唯一的同步容器类!!当两个或多个线程同时访问时也是性能良好的。 Stsck: 这个类从Vector派生而来，并且增加了方法实现栈!一种后进先出的存储结构。 面向位置的操作包括插入某个元素或 Collection 的功能，还包括获取、除去或更改元素的功能。在 List 中搜索元素可以从列表的头部或尾部开始，如果找到元素，还将报告元素所在的位置。 void add(int index, Object element) boolean addAll(int index, Collection collection) Object get(int index) int indexOf(Object element) int lastIndexOf(Object element) Object remove(int index) Object set(int index, Object element)List 接口不但以位置友好的方式遍历整个列表，还能处理集合的子集： ListIterator listIterator() ListIterator listIterator(int startIndex) List subList(int fromIndex, int toIndex)处理subList()时，位于fromIndex的元素在子列表中，而位于toIndex的元素则不是，提醒这一点很重要。以下for-loop 测试案例大致反映了这一点： for (int i=fromIndex; i public static void main(String args[]) { Map map = new HashMap(); Integer ONE = new Integer(1); for (int i=0, n=args.length; i frequency = ONE; } else { int value = frequency.intValue(); frequency = new Integer(value + 1); } map.put(key, frequency); } System.out.println(map); Map sortedMap = new TreeMap(map); System.out.println(sortedMap); } }结果： //无序输出： {prescribed=1, a=1, time=2, any=1, no=1, shall=1, nor=1, peace=1, owner=1, soldier=1, to=1, the=2, law=1, but=1, manner=1, without=1, house=1, in=4, by=1, consent=1, war=1, quartered=1, be=2, of=3} //有序输出： {a=1, any=1, be=2, but=1, by=1, consent=1, house=1, in=4, law=1, manner=1, no=1, nor=1, of=3, owner=1, peace=1, prescribed=1, quartered=1, shall=1, soldier=1, the=2, time=2, to=1, war=1, without=1}解疑： 1、什么是Iterator 一些集合类提供了内容遍历的功能，通过java.util.Iterator接口。这些接口允许遍历对象的集合。依次操作每个元素对象。当使用 Iterators时，在获得Iterator的时候包含一个集合快照。通常在遍历一个Iterator的时候不建议修改集合本省。 2、Iterator与ListIterator有什么区别？ Iterator：只能正向遍历集合，适用于获取移除元素。ListIerator：继承Iterator，可以双向列表的遍历，同样支持元素的修改。 3、什么是HaspMap和Map？ Map是接口，Java 集合框架中一部分，用于存储键值对，HashMap是用哈希算法实现Map的类。 4、HashMap与HashTable有什么区别？对比Hashtable VS HashMap 两者都是用key-value方式获取数据。Hashtable是原始集合类之一（也称作遗留类）。HashMap作为新集合框架的一部分在Java2的1.2版本中加入。它们之间有一下区别： ● HashMap和Hashtable大致是等同的，除了非同步和空值（HashMap允许null值作为key和value，而Hashtable不可以）。 ● HashMap没法保证映射的顺序一直不变，但是作为HashMap的子类LinkedHashMap，如果想要预知的顺序迭代（默认按照插入顺序），你可以很轻易的置换为HashMap，如果使用Hashtable就没那么容易了。 ● HashMap不是同步的，而Hashtable是同步的。 ● 迭代HashMap采用快速失败机制，而Hashtable不是，所以这是设计的考虑点。 5、在Hashtable上下文中同步是什么意思？ 同步意味着在一个时间点只能有一个线程可以修改哈希表，任何线程在执行hashtable的更新操作前需要获取对象锁，其他线程等待锁的释放。 6、什么叫做快速失败特性 从高级别层次来说快速失败是一个系统或软件对于其故障做出的响应。一个快速失败系统设计用来即时报告可能会导致失败的任何故障情况，它通常用来停止正常的操作而不是尝试继续做可能有缺陷的工作。当有问题发生时，快速失败系统即时可见地发错错误告警。在Java中，快速失败与iterators有关。如果一个iterator在集合对象上创建了，其它线程欲“结构化”的修改该集合对象，并发修改异常 （ConcurrentModificationException） 抛出。 7、怎样使Hashmap同步？ HashMap可以通过Map m = Collections.synchronizedMap（hashMap）来达到同步的效果。 8、什么时候使用Hashtable，什么时候使用HashMap 基本的不同点是Hashtable同步HashMap不是的，所以无论什么时候有多个线程访问相同实例的可能时，就应该使用Hashtable，反之使用HashMap。非线程安全的数据结构能带来更好的性能。 如果在将来有一种可能—你需要按顺序获得键值对的方案时，HashMap是一个很好的选择，因为有HashMap的一个子类 LinkedHashMap。所以如果你想可预测的按顺序迭代（默认按插入的顺序），你可以很方便用LinkedHashMap替换HashMap。反观要是使用的Hashtable就没那么简单了。同时如果有多个线程访问HashMap，Collections.synchronizedMap（）可以代替，总的来说HashMap更灵活。 9、为什么Vector类认为是废弃的或者是非官方地不推荐使用？或者说为什么我们应该一直使用ArrayList而不是Vector 你应该使用ArrayList而不是Vector是因为默认情况下你是非同步访问的，Vector同步了每个方法，你几乎从不要那样做，通常有想要同步的是整个操作序列。同步单个的操作也不安全（如果你迭代一个Vector，你还是要加锁，以避免其它线程在同一时刻改变集合）.而且效率更慢。当然同样有锁的开销即使你不需要，这是个很糟糕的方法在默认情况下同步访问。你可以一直使用Collections.sychronizedList来装饰一个集合。 事实上Vector结合了“可变数组”的集合和同步每个操作的实现。这是另外一个设计上的缺陷。Vector还有些遗留的方法在枚举和元素获取的方法，这些方法不同于List接口，如果这些方法在代码中程序员更趋向于想用它。尽管枚举速度更快，但是他们不能检查如果集合在迭代的时候修改了，这样将导致问题。尽管以上诸多原因，Oracle也从没宣称过要废弃Vector。 |
1.Collection接口 Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。 所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个 Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。 如何遍历Collection中的每一个元素？不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下：
由Collection接口派生的两个接口是List和Set。 2.Set【本文地址】
今日新闻 |
推荐新闻 |